
#include<iostream>

template<typename T>
class LinkList
{
public:

    LinkList();
    ~LinkList();


    // 尾插法
    void InsertTail(const T& elemnet);

    // 头插法
    void InsertHead(const T & element);

    // 中间插
    void InsertByIndex(int index,const T & element);
    
    //按位置删除
    void RemoveByIndex(int index);
    
    //按值删除
    void RemoveByElement(const T & element);
    
    // 按位置查找
    T* FindByIndex(int index);
    
    void show();
    



    template<typename U>
    friend std::ostream& operator<<(std::ostream & os,const LinkList<U>& list);






private:
   
    struct Node
    {
        Node(const T& element)
        {
            data =element;
            next = nullptr;
        }
        T data;  //链表 模板  的参数化的 是  节点 的数据域
        Node* next;
    };

    Node* head;

    int size;

};


template<typename T>
LinkList<T>::LinkList():size(0)
{
    //模板支持 匿名对象
    head = new Node( T() );
}
template<typename T>
LinkList<T>::~LinkList()
{
    while(head != nullptr)
    {
        Node* nextNode = head ->next;//记下下一个结点
        delete head;
        head = nextNode;// 结点往后走
    }
}
template <typename T>
inline void LinkList<T>::InsertTail( const T& element)
{
    Node *travelPoint = head;
    while (travelPoint->next != nullptr)
    {
        travelPoint = travelPoint->next;
    }
    travelPoint->next = new Node(element); //()小括号在这里是初始化的作用，相当于调用构造函数
    
    size++; 
}

template <typename T>
inline void LinkList<T>::InsertHead(const T &element)
{
    Node* newNode = new Node(element);
    newNode->next = head->next;
    head->next = newNode;
    size++;
}

template <typename T>
inline void LinkList<T>::InsertByIndex(int index, const T &element)
{
     Node* travelPoint = head;
    for(int i=0;i<index;i++)
    {
        travelPoint = travelPoint->next;
    }
    Node* newNode = new Node(element);
    newNode->next = travelPoint->next;
    travelPoint->next = newNode;
    size++;
}






template <typename T>
void RemoveByIndex(int index)
{
 if(index<0 || index >= size)
    {
        std::cout<<"非法的删除位置\n";
        return;
    }
    Node* travelPoint = head;
    for(int i=0;i<index;i++)
    {
        travelPoint = travelPoint->next;
    }
    Node* freeNode = travelPoint->next;

    travelPoint->next = freeNode->next;

    delete freeNode;
    size--;
}



template <typename T>
void LinkList<T>::RemoveByElement(const T &element)
{
    Node *travelPoint = head;
    while (travelPoint->next != nullptr)
    {
        if(travelPoint->next->data == element)
        {
            Node* freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            delete freeNode;
            size--; 
        }
        else
        travelPoint = travelPoint->next;
    }
}













template <typename T>
void LinkList<T>::show()
{
    Node *travelPoint = head->next;
    
    std::cout<<"size:"<<this->size<<std::endl;
    
    while (travelPoint != nullptr)
    {   
        std::cout<< travelPoint->data <<" ";
        
        travelPoint = travelPoint->next;
    }
    std::cout<<std::endl;
}




template <typename U>
inline std::ostream &operator<<(std::ostream &os, const LinkList<U> &list)
{
    
    //关键字： typename   ：声明后面跟着的 模板 是一个类型
    
    typename LinkList<U>::Node* travelPoint = list.head->next;
    
    std::cout<<"size:"<<list.size<<std::endl;
    while (travelPoint != nullptr)
    {   
        std::cout<< travelPoint->data <<" ";
        
        travelPoint = travelPoint->next;
    }
    std::cout<<std::endl;
    return os;
}



















